W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
W Bajtocji niedawno zbudowano staw, w którym mieszka żółwi. W każdym z domków, ponumerowanych od 1 do , które się tam znajdują, mieszka dokładnie jeden żółw. W najbliższym czasie do Bajtocji planuje wpaść w odwiedziny rak Wędrownik mieszkający na co dzień w Bajtomeryce. Jest on rakiem bardzo towarzyskim i wszystkie bajtockie żółwie są jego przyjaciółmi. Podczas swojego pobytu, Wędrownik chce się zatrzymać w domku u jednego z nich. Tu powstaje jednak dylemat - wktórym domku powinien mieszkać?
Wędrownika interesują przede wszystkim takie domki, z których mógłby odwiedzać jak najwięcej przyjaciół. Mogłoby się wydawać, że odwiedzanie przyjaciół to żaden problem, ale jednak w bajtockim stawie jest to w pewien sposób utrudnione. Po pierwsze, aby kogoś odwiedzić, trzeba się najpierw dostać do jego domku. Po drugie, trzeba później wrócić z powrotem. Zakładamy również, że Wędrowiec nie odwiedza żółwia, u którego mieszka.
Wędrowiec porusza się zgodnie z następującymi zasadami:
Napisz program, który:
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite i (, ), oznaczające odpowiednio ilość domków i ilość tras. W kolejnych wierszach znajdują się opisy poszczególnych tras, po jednym w każdym wierszu. Opis trasy składa się z trzech liczb , i (, ). Liczba to numer domku, w którym trasa się zaczyna, to numer domku, w którym się kończy. Trasa jest specjalna, jeśli .
Twój program powinien wypisać na standardowe wyjście dokładnie wierszy. W -tym z nich powinna się znaleźć liczba przyjaciół, których mógłby odwiedzić Wędrowiec, gdyby mieszkał w domku numer .
Dla danych wejściowych:
5 5 2 1 1 2 3 0 3 4 0 4 2 0 5 3 1
poprawną odpowiedzią jest:
3 3 3 3 0
Mieszkając w domku numer 1, rak może odwiedzić przyjaciół w domkach 2, 3, 4. Mieszkając w domku numer 2, rak może odwiedzić przyjaciół w domkach 3, 4, 5. Mieszkając w domku numer 3, rak może odwiedzić przyjaciół w domkach 2, 4, 5. Mieszkając w domku numer 4, rak może odwiedzić przyjaciół w domkach 2, 3, 5. Mieszkając w domku numer 5, rak nie może odwiedzić żadnego przyjaciela.
Autor zadania: Szymon Acedański.